/**
 * 
 */
package tree.passed;

/**
 * @author xyyi
 *
 */
public class UniValueBinaryTree {

	/**
	 http://mattcb.blogspot.com/2012/11/uni-value-subtree-problem.html
	 uni value subtree problem
	find the number of the uni value subtrees in a binary tree, that is each subtree contain only the same value as itself 
	such that : 
	  1 
	return 1 {1} 
	   1 
	  1 1 
	return 3 {1,1,{1,1,1}} 
	     1 
	   2  3 
	return 2  {2, 3} 
	    1 
	   2  3 
	  2 
	return 3 { 2, {2,2}, 3} 
	
	     1 
	   2   3 
	  2 
	4 
	return 2 {4,3} 
	 */
	int count = 0;

	public boolean findNumberOfUniValueTreeGV(TreeNode root) {
		if (root == null)
			return true;
		boolean left = findNumberOfUniValueTreeGV(root.left);
		boolean right = findNumberOfUniValueTreeGV(root.right);
		if (left && right && (root.left == null || root.val == root.left.val)
		        && (root.right == null || root.val == root.right.val)) {
			count++;
			return true;
		}

		return false;
	}

	/*
	 * int[] with 2 value
	 * int[0] the number of uni value tree from this root node
	 * int[1] 0 mean this subtree is not uni value tree, 1 mean it is
	 */
	public int[] findNumberOfUniValueTree(TreeNode root) {
		int[] result = new int[2];
		if (root == null) {
			result[1] = 1;
			return result;
		}
		int[] left = findNumberOfUniValueTree(root.left);
		int[] right = findNumberOfUniValueTree(root.right);
		result[0] = left[0] + right[0];
		if (left[1] == 1 && right[1] == 1
		        && (root.left == null || root.val == root.left.val)
		        && (root.right == null || root.val == root.right.val)) {
			result[0]++;
			result[1] = 1;
		}

		return result;
	}

	/**
	 * 
	 */
	public UniValueBinaryTree() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * Definition for binary tree
	 */

	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
